package com.arithmetic.basics;

import com.util.ListNode;

/**
 * 给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。
 * 示例 1：
 * 输入：head = [2,4,7,8], cnt = 1
 * 输出：8
 * 提示：
 * 1 <= head.length <= 100
 * 0 <= head[i] <= 100
 * 1 <= cnt <= head.length
 * Related Topics
 * 链表
 * 双指针
 */
public class Day26 {
    public ListNode trainingPlan(ListNode head, int cnt) {
// 这种方法就像两个人一起跑步，一个人先跑 cnt 步，然后两个人再一起跑。当先跑的人到达终点时，后面那个人正好跑到了倒数第 cnt 个位置。这就是代码的工作原理！
//        初始化两个指针：p和q，
        ListNode p, q; // 声明两个ListNode类型的指针p和q
        p = head;// 初始化链表的头节点head
        q = head;
//        先让p移动cnt个节点
        while (cnt > 0) {
            cnt--;
            p = p.next;
        }
//        然后同时移动p和q，直到p到达末尾
        while (p != null) { // 只要p不为空，则继续循环
            p = p.next;
            q = q.next;
        }
//        此时指向q指向的就是倒数第cnt个节点
        return q;
    }

    /**
     * @param head 头结点
     * @param cnt  移动部署
     * @return
     */
    public ListNode trainingPlna2(ListNode head, int cnt) {
        ListNode p, q;
        p = head;
        q = head; // 初始化头结点
        while (cnt > 0) {
            cnt--;
            p = p.next;
        }
        while (p != null) {
            p = p.next;
            q = q.next;
        }
        return q;
    }

}
